package DP;

/**
 * https://www.lintcode.com/problem/paint-house/description
 */
public class PaintHouse {
    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCost(int[][] costs) {
        // write your code here
        int length = costs.length;
        int[][] dp = new int[3][length];

        if(length == 0){
            return 0;
        }

        /**
         * 1.转移方程 f(x) = min( min(f(x-1)[1] + costs[x][1]), min(f(x-1)[1] + costs[x][1]))
         */
        //初始第一个房子
        dp[0][0] = costs[0][0];
        dp[0][1] = costs[0][1];
        dp[0][2] = costs[0][2];

        //开始计算后续的数字
        for(int i=1; i<length; i++){
            dp[i][0] = Math.min(dp[i-1][1] + costs[i][0], dp[i-1][2] + costs[i][0]);
            dp[i][1] = Math.min(dp[i-1][0] + costs[i][1], dp[i-1][2] + costs[i][1]);
            dp[i][2] = Math.min(dp[i-1][1] + costs[i][2], dp[i-1][0] + costs[i][2]);
        }

        return Math.min(Math.min(dp[length - 1][0], dp[length - 1][1]) , Math.min(dp[length - 1][1], dp[length - 1][2]));
    }


    /**
     * @param costs: n x 3 cost matrix
     * @return: An integer, the minimum cost to paint all houses
     */
    public int minCostII(int[][] costs) {
        // write your code here
        int n = costs.length;
        int k = costs[0].length;

        int[][] dp = new int[n+1][k];
        for(int i=0; i<n; i++){
            dp[i][0] = 0;
        }
        int min1,min2;
        int c1=0,c2=0;
        for(int i=1; i<=n; i++){
            //先找出来上一次DP中，数值最小的2个颜色，然后，新的计算只需要和这两个计算就可以了。
            min1=min2=Integer.MAX_VALUE;//要注意，这个要放这一行，用这个来替代掉 原本要进行的min()所有的

            for(int j=0;j<k;j++){
                //这里找出来最小的，还有对应其坐标
                if( dp[i-1][j] < min1 ){//dp比目前的还小，就更新。这个要注意
                    //先交换保存min1的信息
                    min2 = min1;
                    c2 = c1;
                    min1 = dp[i-1][j];
                    c1 = j;
                }else if( dp[i-1][j] < min2){//判断跟min2的关系
                    min2 = dp[i-1][j];
                    c2 = j;
                }
            }

            for(int j=0; j<k; j++){
                //因为颜色不能一样，这里要判断下，才能决定用哪个颜色
                dp[i][j] = costs[i-1][j];
                if( j != c1){
                    dp[i][j] += min1;
                }else{
                    dp[i][j] += min2;
                }
            }
        }

        //这个就跟之前一样了，所有的结果，都在最后一排房子，直接从最后一排房子里取哪种颜色的 最低就可以了
        int min = Integer.MAX_VALUE;
        for(int i=0; i<k; i++){
            min = Math.min(min, dp[n][i]);
        }

        return min;
    }

    public static void main(String[] args){
        int[] n = new int[]{-1,1,1,1};

    }

}